package b_sorting_advance.b_quick_sort;

import org.junit.Test;
import utils.ArrayGeneric;
import utils.sorting_helper.SortingHelper;
import utils.sorting_helper.SortingTest;

/**
 * @Author: DeLucia
 * @Description: 快速排序号称20世界最重要的算法之一
 * @Date: 2019/1/24 0:48.
 */
@SuppressWarnings("unchecked")
public class QuickSorting3Ways extends SortingTest {

    @Override
    public void sort(ArrayGeneric arr) {
        quickSort3ways(arr, 0, arr.length() - 1);
    }

    /**
     * 三路快速排序
     * <p>
     * 二路快速排序的问题
     * 1. 当重复元素多的时候向左右两边存放, 浪费一定时间
     * 优化
     * 3. 从左侧扫描 数据分成三路存放, 小于ref的放左路,大于ref的放右路,等于ref的不需动(中路)
     * <p>
     * 一般语言系统的排序底层实现就是使用的三路快速排序
     * 虽然一般情况下速度略不如两路快速排序
     * 但是在出现大量重复元素的时候 三路 的速度更加快速
     *
     * @param arr
     * @param l
     * @param r
     */
    private void quickSort3ways(ArrayGeneric arr, int l, int r) {

        if (r - l <= 15) {
            insertionSort(arr, l, r);
            return;
        }

        // 采用三路分区法
        // 优化 选取随机元素作为基准
        arr.swap(l, (int) (Math.random() * (r - l + 1) + l)); // l0r4 range 0-4 5

        Comparable ref = arr.get(l); // 默认将l所在元素当做参考值进行分区

        int lt = l; // l+1..lt < ref
        int gt = r + 1; // gt..r > ref
        int i = l + 1; // 从l+1开始向右扫描  lt+1..i == ref

        while (i < gt) {
            if (arr.get(i).compareTo(ref) < 0) {
                arr.swap(i, lt + 1);
                i++;
                lt++;
            } else if (arr.get(i).compareTo(ref) > 0) {
                arr.swap(gt - 1, i);
                gt--;
            } else {
                i++;
            }
        }
        arr.swap(l, lt);

        // 对左路和中路递归排序
        quickSort3ways(arr, l, lt - 1);
        quickSort3ways(arr, gt, r);
    }

    /**
     * 当递归到数组规模小于16的时候
     * 为了提高性能改用插入排序
     *
     * @param arr
     * @param left
     * @param right
     */
    private void insertionSort(ArrayGeneric arr, int left, int right) {
        for (int i = left + 1; i <= right; i++) {
            Comparable e = arr.get(i);
            int j;
            for (j = i; j > left && arr.get(j - 1).compareTo(e) > 0; j--) {
                arr.put(j, arr.get(j - 1));
            }
            arr.put(j, e);
        }
    }

    @Test
    public void testingquickSort3ways() {
        ArrayGeneric arr = getRandomIntegerArray(20, 0, 9);
        System.out.println(arr);
        quickSort3ways(arr, 0, arr.length() - 1);
        System.out.println(arr);
    }

    @Test
    public void testingSortMethod() {
        ArrayGeneric arr = getRandomIntegerArray(5000000, 0, 10);
//        System.out.println(arr);
        long begin = System.currentTimeMillis();
        sort(arr);
        long end = System.currentTimeMillis();
//        System.out.println(arr);
        assert SortingHelper.testSorted(arr);
        System.out.println((end-begin) + "ms");
    }

    @Test
    public void testingSortHelperMethod() {
        ArrayGeneric arr = getRandomIntegerArray(5000000, 0, 10);
        new QuickSorting3Ways().testSorting("3 ways quick sort",arr);
    }

    @Test
    public void testRange() {
        int l = 0;
        int r = 19;
        for (int i = 0; i < 20; i++) {
            assert (int) (Math.random() * (r - l + 1) + l) <= 19;
            assert (int) (Math.random() * (r - l + 1) + l) >= 0;
        }
    }

    @Test
    public void testGenerate() {
        ArrayGeneric<Integer> arr1 = getRandomIntegerArray(10, 0, 10);
        System.out.println(arr1);
        ArrayGeneric arr = getNearlySortedIntegerArray(10, 1);
        System.out.println(arr);

    }

}
